//翻转数位
class Solution {
public:
    int reverseBits(int num) 
    {
        //记录两段连续的1 
        //通过 bool flag来判断这两段能不能连接在一起
        bitset<32> set(num);
        int res=1;
        int cnt1=0;int cnt2=0;
        bool flag=false;
        int index=0;
        while(index<32)
        {
            cnt2=0;
            while(index<32 && set[index] )
            {
                index++;
                cnt2++;
            }
            res=max(res,flag?(cnt1+cnt2+1):(cnt2+1));
            cnt1=cnt2;
            cnt2=0;
            while(index<32 && !set[index])
            {
                index++;
                cnt2++;
            }
            if(cnt2==1) flag=true;
            else flag=false;
        }
        //如果值为-1则 cnt2等于32 res=32+1=33
        return min(res,32);
    }
};

//括号
class Solution {
public:
    vector<string>res;
    string tmp;
    vector<string> generateParenthesis(int n) 
    {
        dfs(n,0,0);
        return res;
    }
    void dfs(int n,int left,int right)
    {
        if(tmp.size()==2*n)
        {
            res.push_back(tmp);
            return;
        }
        if(left<n)
        {
            tmp.push_back('(');
            dfs(n,left+1,right);
            tmp.pop_back();
        }
        if(left>right)
        {
            tmp.push_back(')');
            dfs(n,left,right+1);
            tmp.pop_back();
        }
    }
};

//颜色填充
class Solution {
public:
    int arr[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) 
    {
        int target=image[sr][sc];
        dfs(image,target,newColor,sr,sc);
        return image;
    }

    void dfs(vector<vector<int>>& image,int target,int newColor,int x,int y)
    {
        image[x][y]=newColor;
        for(int i=0;i<4;i++)
        {
            int nx=x+arr[i][0];
            int ny=y+arr[i][1];
            if(nx<0 || nx >=image.size() || ny<0 || ny>=image[0].size() || image[nx][ny]==newColor) continue;
            if(image[nx][ny]==target)
            {
                dfs(image,target,newColor,nx,ny);
            }
        }
    }
    /*
    1 1 1   2 2 2
    1 1 0   2 2 0
    1 0 1   2 0 1
    */
};
//硬币
class Solution {
public:
    int mod = 1000000007;
    int waysToChange(int n) 
    {
        //完全背包
        vector<int>dp(n+1);
        int coins[4]={1,5,10,25};
        dp[0]=1;
        for(int i=0;i<4;i++)
        {
            for(int j=coins[i];j<=n;j++)
            {
                dp[j]=(dp[j]+dp[j-coins[i]])%mod;
            }
        }
        return dp[n];
    }
};